import javafx.scene.control.SelectionMode;
import javafx.scene.effect.Blend;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class QuickySort {
    public static void main(String[] args) {
        //int[] array = {1,5,2,3,4,6,9,8,7,10,11,12,13};
        int[] array = {5,3,2,1};
        //quickSort(array,0, array.length-1);
        System.out.println(Arrays.toString(array));
        System.out.println("排序后");
        hoarequickSort(array,0, array.length-1);
        //Sort(array,0, array.length-1);
        //quickSort(array);
        System.out.print(Arrays.toString(array));
    }

    /**
     * 最好时间复杂度：N*logN
     * 最坏时间复杂度：N^2
     * @param elem
     * @param start
     * @param end
     */
    //挖坑法
    public static void quickSort(int[] elem,int start,int end){
        int left = start;
        int right = end;
        if(left >= right){
            return;
        }
        //找基准值的下标，使基准值左边的值小于基准值，基准值右边的值大于基准值
        int tmp = elem[left];
        while (left < right){
               while (left < right && elem[right] >= tmp){
                   right--;
               }
               elem[left] = elem[right];
               while (left < right && elem[left] <= tmp){
                   left++;
               }
               elem[right] = elem[left];
        }
        //将基准值放到基准下标
        elem[left] = tmp;
        //当left等于right的时候，基准值下标找到了
        int benchmark = left;
        //通过递归再次在基准值左右两边再次找基准
        //找左边基准值
        quickSort(elem,start,benchmark-1);
        //找右边基准值
        quickSort(elem,benchmark+1,end);
    }
    //hoare法
    public static void hoarequickSort(int[] elem,int start,int end){
        int left = start;
        int right = end;
        if(left >= right){
            return;
        }
        //找基准值的下标，使基准值左边的值小于基准值，基准值右边的值大于基准值
        /*int tmp = elem[left];
        while (left < right){
            while (left < right && elem[right] >= tmp){
                right--;
            }
            while (left < right && elem[left] <= tmp){
                left++;
            }
            swap(elem,left,right);
        }
        //将基准值放到基准下标
        elem[left] = tmp;
        //当left等于right的时候，基准值下标找到了

         */
        int benchmark = partiotion1(elem,left,right);
        //通过递归再次在基准值左右两边再次找基准
        //找左边基准值
        quickSort(elem,start,benchmark-1);
        //找右边基准值
        quickSort(elem,benchmark+1,end);
    }
    public static void swap(int elem[],int i, int j){
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }
    //用三位取中法对快排进行优化
    public static void Sort(int[] elem,int start,int end){
        int left = start;
        int right = end;
        if(left >= right){
            return;
        }
        //找基准值的下标，使基准值左边的值小于基准值，基准值右边的值大于基准值
        //三数取中法找到更适合当基准值的数的下标
        int index = midThree(elem,start,end);
        //交换更合适当基准值的位置和排序开始的位置
        swap(elem,index,start);
        int tmp = elem[left];
        while (left < right){
            while (left < right && elem[right] >= tmp){
                right--;
            }
            elem[left] = elem[right];
            while (left < right && elem[left] <= tmp){
                left++;
            }
            elem[right] = elem[left];
        }
        //将基准值放到基准下标
        elem[left] = tmp;
        //当left等于right的时候，基准值下标找到了
        int benchmark = left;
        //通过递归再次在基准值左右两边再次找基准
        //找左边基准值
        quickSort(elem,start,benchmark-1);
        //找右边基准值
        quickSort(elem,benchmark+1,end);
    }
    public static int midThree(int[] array,int left,int right){
        int mid = (left+right)/2;
        if(array[left] < array[right]){
            if(array[mid] < array[left]){
                return left;
            }else if(array[mid] > array[right]){
                return right;
            }else {
                return mid;
            }
        }else{
            if(array[mid] > array[left]){
                return left;
            }else if(array[mid] < array[right]){
                return right;
            }else {
                return mid;
            }
        }
    }
    //非递归实现快速排序

    /**
     * 用栈来帮助实现快速排序
     * @param arr
     */
    public static void quickSort(int[] arr) {
        Deque<Integer> stack = new LinkedList<>();
        int left = 0;
        int right = arr.length - 1;
        int privot = partiotion(arr,left,right);
        if(privot > left+1){
            stack.push(left);
            stack.push(privot -1);
        }
        if(privot < right-1){
            stack.push(privot+1);
            stack.push(right);
        }
        while (!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            privot = partiotion(arr,left,right);
            if(privot > left+1){
                stack.push(left);
                stack.push(privot-1);
            }
            if(privot < right-1){
                stack.push(privot+1);
                stack.push(right);
            }
        }
    }
    public static int partiotion(int[] elem,int start,int end){
        int left = start;
        int right = end;
        int tmp = elem[left];
        while (left < right){
            while (left < right && elem[right] >= tmp){
                right--;
            }
            //elem[left] = elem[right];
            while (left < right && elem[left] <= tmp){
                left++;
            }
            //elem[right] = elem[left];
            swap(elem,left,right);
        }
        //将基准值放到基准下标
        elem[left] = tmp;
        //当left等于right的时候，基准值下标找到了
        return left;
    }
    public static int partiotion1(int[] elem,int left,int right){
        int tmp = elem[left];
        int i = left;
        while (left < right){
            while (left < right && elem[right] >= tmp){
                right--;
            }
            //elem[left] = elem[right];
            while (left < right && elem[left] <= tmp){
                left++;
            }
            //elem[right] = elem[left];
            swap(elem,left,right);
        }
        //将基准值放到基准下标
        swap(elem,left,i);
        //当left等于right的时候，基准值下标找到了
        return left;
    }

}
